package com.salim.leetcode.$123;

public class BestTimeToBuyAndSellStockIII {
    //分两次遍历
    //第一次正向 每走一步记一下当前index下最大收益
    //第二次反向 每走一步记一下当前index下最大收益
    //将两次收益相加取最大值
    //如何算最大收益？
    //按照2的方式算上升趋势
    //记录最低的趋势起点
    //记录最大值
    //每次计算最低点到上升趋势最高点的结果与最大值比较存入数组
    public int maxProfit(int[] prices) {
        int[] maxProfitArray = new int[prices.length];
        //先左
        int lowestIndex = 0;
        int maxProfit = 0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[i-1]){
                maxProfit = Math.max(maxProfit,prices[i]-prices[lowestIndex]);
            }else if(prices[i]<prices[i-1]){
                if(prices[i]<prices[lowestIndex]){
                    lowestIndex = i;
                }
            }
            maxProfitArray[i] = maxProfit;
        }
        maxProfit = Math.max(maxProfit,prices[prices.length-1]-prices[lowestIndex]);
        maxProfitArray[prices.length-1] = maxProfit;
        //后右
        int highestIndex = prices.length-1;
        for(int i=prices.length-2;i>0;i--){
            if(prices[i]<prices[i+1]){
                maxProfit = Math.max(maxProfit,prices[highestIndex]-prices[i]+maxProfitArray[i-1]);
            }else if(prices[i]>prices[i+1]){
                if(prices[i]>prices[highestIndex]){
                    highestIndex = i;
                }
            }
            maxProfitArray[i-1] = maxProfit;
        }
        return maxProfit;
    }
}
